Entropy coding in conventional video coding technologies mainly adopts run-length coding and arithmetic coding. For example, in the H.264 coding standard, a context-based adaptive variable length coder (CAVLC) and a context-based adaptive binary arithmetic coder (CABAC) are used. The two entropy coding modes fully utilize correlation between encoded information and information that needs to be encoded currently. Specifically, a code table or a probability model of information that needs to be encoded currently is built by using the encoded information, which is called context-based entropy coding. Due to using an arithmetic encoding idea, the CABAC has better coding performance than the CAVLC, but increases complexity greatly. Because context information is used, current coding information cannot be encoded until adjacent coding information is encoded completely, while parallel operations cannot be performed. As a result, the entropy coding algorithm becomes a bottleneck in the encoding and decoding. To increase the encoding efficiency, a High Efficiency Video Coding (HEVC) video coding standard being established, which is a next generation video compression standard, proposes the following arithmetic coding processes:
A. Encode a map of non-zero transform coefficients (significance map). In this step, an entire transform coefficient block that needs to be encoded is encoded in predetermined scan order, which is also called wide-range scan mode, for example, wide-range Z-shaped (zig-zag) mode; the predetermined scan order may also be scan order in wide-range vertical or wide-range horizontal mode, and accordingly, when encoding is performed subsequently in sub-block mode, scan order in narrow-range vertical mode or in narrow-range horizontal mode is used.
In a process of performing step A, each frequency corresponds to a position in a map. When a frequency is 0, the value of a corresponding position in the map is 0; when the frequency is a non-zero value, the value of the corresponding position in the map is 1. In addition, whether a current frequency is a last non-zero frequency is judged. If the current frequency is the last non-zero frequency, the value of the corresponding position is 1 1 (two 1s rather than eleven); otherwise, the value of the position is 1 0 (1 and 0 rather than ten). In the process of encoding the map, if 1 1 appears in the sequence of 0s and 1s representing the map, it is determined that a transform coefficient block is encoded completely.
B. Encode a map of transform coefficients greater than 1 in sub-block mode. In this step, a map of transform coefficients greater than 1 in the entire transform coefficient block is encoded in predetermined scan order, which is also called narrow-range scan mode, for example, narrow-range zig-zag mode.
C. Encode absolute values of coefficients greater than 1 in sub-block mode by using a narrow-range zig-zag mode.
D. Encode positive and negative signs of non-zero coefficients in sub-block mode and by using a narrow-range zig-zag mode. The foregoing steps B to D are performed on a cyclic basis until all the sub-blocks are encoded completely.
In the foregoing steps, the sub-block mode is defined as follows by using an 8×8 transform coefficient block as an example: An upper left 4×4 transform coefficient block is encoded firstly, followed by an upper right 4×4 transform coefficient block, a lower left 4×4 transform coefficient block, and a lower right 4×4 transform coefficient block. The foregoing 4×4 transform coefficient blocks are sub-blocks of an 8×8 transform coefficient block. The scan order of the wide-range zig-zag mode and the scan order of the narrow-range zig-zag mode are illustrated in FIG. 1A and FIG. 1B respectively, where each small box represents a frequency, and the numbers in the boxes represent the scan order. It is evident that the scan order of the wide-range zig-zag mode and the narrow-range zig-zag mode is based on the same scan rule. For different scanned objects, however, from the perspective of the entire transform coefficient block, the scan order is different between step A of encoding the significance map and step B to step D of encoding absolute values (levels) of transform coefficients and encoding positive and negative signs of non-zero transform coefficients. Due to different scan order, data needs to be read once respectively in the process of performing step A and performing step B to step D; and two table lookup modes corresponding to the two order types need to be fixed at a decoding end, causing high encoding and decoding overheads and low efficiency. In addition, in step A, if the transform coefficient block is relatively large, which is usually called a large transform unit, for example, a 32×32 significance map, encoding a large significance map causes a heavy burden during hardware designs.